Search results for "Universal graph"

showing 2 items of 2 documents

Two graphs with a common edge

2014

Let G = G1 ∪ G2 be the sum of two simple graphs G1,G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant det A(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples

Discrete mathematicsBlock graphadjacency matrixcycleApplied MathematicsSymmetric graphpathComparability graphgraphdeterminant of graphlaw.inventionCombinatoricsPathwidthlawOuterplanar graphLine graphQA1-939Discrete Mathematics and CombinatoricsMathematicsMathematicsUniversal graphDistance-hereditary graphDiscussiones Mathematicae Graph Theory
researchProduct

Distance graphs and the T-coloring problem

1999

Abstract The T-coloring problem is, given a graph G = (V, E), a set T of nonnegative integers containing 0, and a ‘span’ bound s ⩾ 0, to compute an integer coloring f of the vertices of G such that |f(ν) − f(w)| ∉ T ∀νw ∈ E and max f − min f ⩽ s. This problem arises in the planning of channel assignments for broadcast networks. When restricted to complete graphs, the T-coloring problem boils down to a number problem which can be solved efficiently for many types of sets T. The paper presents results indicating that this is not the case if the set T is arbitrary. To these ends, the class of distance graphs is introduced, which consists of all graphs G : G ≅ G(A) for some (finite) set of posi…

Discrete mathematics1-planar graphTheoretical Computer ScienceCombinatoricsGraph bandwidthGraph powerDiscrete Mathematics and CombinatoricsCographSplit graphGraph coloringComplement graphUniversal graphMathematicsMathematicsofComputing_DISCRETEMATHEMATICSDiscrete Mathematics
researchProduct